/*
面试题 04.06. 后继者
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继, 也就是中序遍历的下一个节点）。

常规思路：
1. 对于普通的二叉树，需要节点提供parent指针指向父节点，才可以实现(root.parent=null)。
判断目标节点是否有右子树，如果有，则后继节点为右子树的最左边节点
如果目标节点没有右子树，则要往上找，找到第一个满足 目标节点所在子树为某个节点的左子树(result.left===该子树root)
此时得到result.

2. 对于二叉搜索树，可以通过元素大小关系，由根节点出发找到这个目标节点的父节点满足上面那个关系的。
通过额外变量来记录往左走的路径，往右走不记录.
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function (root, p) {
  if (root && p) {
    // 有右子树
    if (p.right) {
      p = p.right
      while (p.left) {
        p = p.left
      }
      return p
    } else {
      // 没有右子树
      let cur = root
      let parent = null
      while (cur !== p) {
        if (p.val < cur.val) {
          // 往左走去找p
          parent = cur // 记录左走的路径
          cur = cur.left
        } else {
          cur = cur.right // 右走的不记录
        }
      }
      return parent
    }
  }
}
